כל פקודה תתחיל ב-MKגדולות עש מיכאל קלי (Michael Kali), וזאת משתי סיבות:
כדי שבטבלת הקיצורים שבתוך \SpecialChar LyX תופענה כל הפקודות זו לצד זו.
הבחירה דווקא באותיות גדולות נועדה לוודא שהפקודות אינן מתנגשות עם פקודות \SpecialChar LaTeX מקוריות.
על הפקודות להיות קצרות ככל האפשר, וזאת כדי לאפשר את כתיבתן במהירות מבלי ליצור להן קיצור מקלדת. הסיבה לכך שלא ניצור קיצור מקלדת לכל פקודה היא שפעמים רבות ניצור פקודות שתיועדנה למקרים מסוימים מאוד, ואז יעבור זמן רב עד שנשתמש בקיצור המקלדת בפעם הבאה ולכן לא נזכור אותו - הרבה יותר פשוט לזכור את הפקודה שיצרנו מכיוון שיש לה תוכן אמיתי שקשור לפלט הרצוי מן הפקודה. סיבה נוספת היא שיצירת קיצור מקלדת לכל פקודה ולו החריגה ביותר תקשה עלינו ליצור קיצורי מקלדת לפקודות חשובות יותר. לפיכך פקודות שימושיות מאוד שבוודאי ניצור להן קיצור מקלדת ונשתמש בו פעמים רבות אינן צריכות להיות קצרות.
כדי להקל על כתיבת פקודות שלא יצרתי להן קיצור מקלדת כתבתי קיצור מקלדת שיוצר את הקידומת של כל פקודות ה-macrosשלי ואז כל מה שנותר הוא להקיש שלוש-ארבע אותיות כדי לבחור את הפקודה הרצויה, קיצור המקלדת המדובר הוא "Ctrl+k".
לכל גופן יש קידומת בת שתי אותיות.
\(\:\)
\(\:\)קבוצות ופונקציות לפי קורסיםLatexCommand ruleoffset "0.5ex"width "100col%"height "1pt"\(\:\)
\(\:\)המספרים המרוכבים ופונקציות מרוכבות\(\:\)
\(\newcommand{\MKcis}{\text{cis}}\)\(\cos+i\cdot\sin\). המספרים המרוכבים.
\(\newcommand{\MKre}{\text{Re}}\)החלק הממשי של מספר מרוכב. המספרים המרוכבים.
\(\newcommand{\MKim}{\text{Im}}\)החלק המדומה של מספר מרוכב. המספרים המרוכבים.מופיע גם כתמונה של פונקציה.
סביר להניח שהסיכומים שלי מכילים טעויות רבות - אני מוצא כאלה כל יום (רשימת טעויות נפוצות), אני מפציר בכם לעדכן אותי בכל טעות שאתם מוצאים (ממש כל טעות ללא יוצא מן הכלל); אתם מוזמנים להגיב על המסמכים ב-Google Drive, לשלוח לי דוא“ל או למלא פנייה באתר.
הערה כללית בנושא הלוגיקה: כל מה שנלמד בנושא זה הוא בסה"כ דרך לכתוב דברים שידענו לפני כן, זה לא חומר חדש וכל מי שיודע עברית ומסוגל להשתמש בהגיון ע"מ להבין את התוכן של מה שהוא קורא כבר יודע הכל בנושא זה.
הגדרה 1.1. עקרון השלישי הנמנע פסוק הוא משפט (sentence) היכול לקבל אחד משני ערכים: או שהמשפט נכון או שהוא לא נכון1מקובל לומר שהמשפט מקבל אחד משני ערכים: אמת או שקר, בעברית המילה שקר משמשת לתיאור משפט שהאומר אותו יודע שאינו נכון ואומר זאת בכוונה תחילה, לכן זה קצת בעייתי לדבר על שקר במתמטיקה; באנגלית המושגים המקבילים הם \(\MKtrue\) ו-\(\MKfalse\), עבור האחרון אין מילה מתאימה בעברית (מלבד "לא נכון") ולכן מתמטיקאים משתמשים בתרגום הגרוע ל-"שקר". אך לא תתכן שום אפשרות אחרת (אין דבר כזה "נכון חלקית"), הערך שמקבל הפסוק נקרא ערך האמת של הפסוק.
\(\clubsuit\)
איני רוצה לומר שהגדרה זו היא האקסיומה הקרויה בשם זה (ראו "עקרון השלישי הנמנע" בוויקיפדיה) אלא שכל משפט (sentence) שאינו מקיים את עקרון השלישי הנמנע אינו פסוק (ולהפך, כל משפט המקיים אותו הוא פסוק).
\(\clubsuit\)
לדוגמה: \(x^{2}=x\) אינו פסוק (שכן \(x\) אינו מוגדר) אך הוא אכן משפט.
\(\clubsuit\)
פעולה דו-מקומית (בינארית) היא פעולה2גם למונח פעולה נתייחס לעת עתה כמושג יסוד. המקבלת שני פרטים (לאו דווקא שונים) ומחזירה אחד.
\(\clubsuit\)
בהגדרות הבאות נשתמש בטבלאות אמת כדי לתאר קשרים שונים, בצד שמאל יופיעו כל המקרים האפשריים עבור ערכי האמת של הפסוקים אותם הקשר מקבל (ארבעה מקרים עבור קשר בינארי ושניים עבור קשר אונארי) ובצד ימין יופיעו הערכים שמקבל הפסוק שמחזיר הקשר.
\(\clubsuit\)
במדעי המחשב ישנו קשר נוסף הנקרא "xor"3אין לו סימון מתמטי, נוהגים לקרוא לו גם "או מוציא" כדי להבדילו מ-"או כולל" שבהגדרה הקודמת. המקבל ערך אמת רק כאשר אחד בדיוק משני הפסוקים נכון ואילו רעהו אינו נכון, כלומר (אם נסמן ב-\(\tilde{\vee}\)4זה ממש לא סימון מקובל. את "xor"):
\(P\tilde{\lor}Q\)
\(Q\)
\(P\)
\(\MKfalse\)
\(\MKtrue\)
\(\MKtrue\)
\(\MKtrue\)
\(\MKfalse\)
\(\MKtrue\)
\(\MKtrue\)
\(\MKtrue\)
\(\MKfalse\)
\(\MKfalse\)
\(\MKfalse\)
\(\MKfalse\)
משפטנים נוהגים לכתוב "ו/או" כדי להדגיש שכוונתם ל-"או" כולל ולא ל-"או" מוציא.
\(\clubsuit\)
נשים לב שבניגוד לקשרים "או" ו-"וגם" בקשר "אם-אז" הסדר של הפסוקים משנה את התוצאה: "אם יורד גשם אז יש עננים" הוא פסוק אמת ואילו "אם יש עננים אז יורד גשם" הוא פסוק שקר. למען האמת אין במתמטיקה שני סימונים שהמשמעות הלשונית שלהם זהה (גם אם מבחינה מעשית אין ביניהם שום הבדל והתוצאה זהה), דוגמאות:
\(P\land Q\) הוא "\(P\) וגם \(Q\)" ואילו \(Q\land P\) הוא "\(Q\) וגם \(P\)".
\(P\lor Q\) הוא "\(P\) או \(Q\)" ואילו \(Q\lor P\) הוא "\(Q\) או \(P\)".
\(x<y\) הוא "\(x\) קטן מ-\(y\)" ואילו \(y>x\) הוא "\(y\) גדול מ-\(x\)".
\(\lnot\left(x=y\right)\) הוא "זה לא נכון ש-\(x\) שווה ל-\(y\)" או "\(x\) לא שווה ל-\(y\)" ואילו \(x\neq y\) הוא "\(x\) שונה מ-\(y\)".
ואפילו \(x=y\) ו-\(y=x\) נושאים תוכן שונה מבחינה לשונית: הראשון הוא "\(x\) שווה ל-\(y\)" ואילו השני הוא "\(y\) שווה ל-\(x\)"5במו אוזניי שמעתי מרז שיש הבדל מהותי בין הפסוק \(\lim_{x\rightarrow a}f\left(x\right)=b\) ל-\(b=\lim_{x\rightarrow a}f\left(x\right)\) כאשר הגבול הנ"ל אינו קיים: הראשון אומר שהגבול קיים ושווה ל-\(b\) (ומכיוון שהגבול לא קיים זהו פסוק שקר) ואילו השני אומר ש-\(b\) שווה למשהו שאינו מוגדר ולכן א"א לומר שהוא אינו נכון ועל כן הוא פסוק אמת. לכאורה הגבול לא מוגדר ולכן שני אלו אינם פסוקים, מה קורה פה?.
לכן אם נתבקש לכתוב פסוק שקול ל-\(\lnot\left(x=y\right)\) מבלי להשתמש בשלילה נוכל לכתוב \(x\neq y\).
\(\clubsuit\)
נשים לב למה שאומרת ההגדרה: היא אינה אומרת ש-\(Q\) נכון בגלל ש-\(P\) נכון אלא שבכל המקרים שבהם \(P\) נכון גם \(Q\) נכון, כך למשל הפסוק "אם \(2=2\) אז משפט פיתגורס נכון" הוא פסוק אמת במתמטיקה.
\(\clubsuit\)
מקובל לסמן גם \(Q\leftarrow P\) והמשמעות הלשונית של סימון זה היא "\(Q\) נכון בכל מקרה שבו \(P\) נכון".
\(\clubsuit\)
אם הפסוק \(P\rightarrow Q\) נכון נאמר שתנאי מספיק לכך ש-\(Q\) יתקיים הוא ש-\(P\) מתקיים (נשים לב: ייתכן ש-\(Q\) נכון גם מבלי ש-\(P\) נכון ולכן אין זה תנאי הכרחי), לעומת זאת נאמר שתנאי הכרחי לכך ש-\(P\) יתקיים הוא ש-\(Q\) יתקיים (שהרי \(P\) אינו יכול להיות נכון מבלי ש-\(Q\) נכון6נשים לב לכך שייתכן ש-\(Q\) נכון ולמרות זאת \(P\) אינו נכון ולכן אין זה תנאי מספיק).
הגדרה 1.2. משפט (או טענה) הוא פסוק שמנוסח באופן כללי ע"י שימוש במשתנה שאינו מוגדר, ורק לאחר שמגדירים את המשתנה הופך המשפט לפסוק (כפי הגדרתו לעיל).
הגדרה 1.3. קשרים
קשר בינארי הוא פעולה דו-מקומית המקבלת שני פסוקים ומחזירה פסוק חדש שערך האמת שלו נקבע ע"י הקשר הבינארי ע"פ ערכי האמת של הפסוקים שקיבל.
קשר אונארי הוא פעולה המקבלת פסוק יחיד ומחזירה פסוק יחיד שערך האמת שלו נקבע ע"י הקשר הבינארי ע"פ ערך אמת של הפסוק שקיבל.
הגדרה 1.4. לא (not) הקשר "לא" הוא קשר אונארי המחזיר לכל פסוק \(P\) את הפסוק \(\lnot P\) (קרי: לא \(P\)) שמקבל ערך אמת כאשר \(P\) נכון ומקבל ערך שקר כאשר \(P\) אינו נכון, כלומר:
\(\lnot P\)
\(P\)
\(\MKfalse\)
\(\MKtrue\)
\(\MKtrue\)
\(\MKfalse\)
הגדרה 1.5. וגם (and) הקשר "וגם" הוא קשר בינארי המחזיר לכל שני פסוקים \(P\) ו-\(Q\) את הפסוק \(P\land Q\) (קרי: \(P\) וגם \(Q\)) שמקבל ערך אמת כאשר \(P\) ו-\(Q\) שניהם נכונים ומקבל ערך שקר בכל מקרה אחר, כלומר:
\(P\land Q\)
\(Q\)
\(P\)
\(\MKtrue\)
\(\MKtrue\)
\(\MKtrue\)
\(\MKfalse\)
\(\MKfalse\)
\(\MKtrue\)
\(\MKfalse\)
\(\MKtrue\)
\(\MKfalse\)
\(\MKfalse\)
\(\MKfalse\)
\(\MKfalse\)
הגדרה 1.6. או (or) הקשר "או" הוא קשר בינארי המחזיר לכל שני פסוקים \(P\) ו-\(Q\) את הפסוק \(P\lor Q\) (קרי: \(P\) או \(Q\)) שמקבל ערך אמת כאשר לפחות אחד מבין שני הפסוקים \(P\) ו-\(Q\) נכון ומקבל ערך שקר כאשר שניהם אינם נכונים, כלומר:
\(P\lor Q\)
\(Q\)
\(P\)
\(\MKtrue\)
\(\MKtrue\)
\(\MKtrue\)
\(\MKtrue\)
\(\MKfalse\)
\(\MKtrue\)
\(\MKtrue\)
\(\MKtrue\)
\(\MKfalse\)
\(\MKfalse\)
\(\MKfalse\)
\(\MKfalse\)
הגדרה 1.7. אם-אז (if) הקשר "אם-אז" הוא קשר בינארי המחזיר לכל שני פסוקים \(P\) ו-\(Q\) את הפסוק \(P\rightarrow Q\) (קרי: אם \(P\) אז \(Q\) או: \(P\) גורר את \(Q\)) האומר שבכל מקרה שבו \(P\) נכון \(Q\) נכון, כלומר:
\(P\rightarrow Q\)
\(Q\)
\(P\)
\(\MKtrue\)
\(\MKtrue\)
\(\MKtrue\)
\(\MKfalse\)
\(\MKfalse\)
\(\MKtrue\)
\(\MKtrue\)
\(\MKtrue\)
\(\MKfalse\)
\(\MKtrue\)
\(\MKfalse\)
\(\MKfalse\)
טענה 1.8. אם \(P\rightarrow Q\) וגם \(Q\rightarrow R\) אז \(P\rightarrow R\).
הגדרה 1.9. אם ורק אם (if and only if)7מקובל לקצר ולכתוב אם"ם או אםם (ובאנגליתiff).
הקשר "אם ורק אם" הוא קשר בינארי המחזיר לכל שני פסוקים \(P\) ו-\(Q\) את הפסוק \(P\longleftrightarrow Q\) (קרי: \(P\) אם ורק אם \(Q\)) האומר ש-\(P\) נכון אם \(Q\) נכון ורק כאשר \(Q\) נכון \(P\) נכון, כלומר:
\(P\longleftrightarrow Q\)
\(Q\)
\(P\)
\(\MKtrue\)
\(\MKtrue\)
\(\MKtrue\)
\(\MKfalse\)
\(\MKfalse\)
\(\MKtrue\)
\(\MKfalse\)
\(\MKtrue\)
\(\MKfalse\)
\(\MKtrue\)
\(\MKfalse\)
\(\MKfalse\)
\(\clubsuit\)
ניתן לומר גם שהקשר "אם ורק אם" אומר שאם \(P\) אז \(Q\) וגם אם \(Q\) אז \(P\) (זה גם מסתדר עם הסימון שלו), כלומר \(P\longleftrightarrow Q=\left(P\rightarrow Q\right)\land\left(Q\rightarrow P\right)\).
\(\clubsuit\)
למעשה, למרות שהניסוח הלשוני נראה חסר סימטריה הקשר "אם ורק אם" אינו מתחשב בסדר הפסוקים ואמר ששניהם מקבלים את אותו ערך אמת בכל מקרה, רוצה לומר הם שקולים זה לזה.
\(\clubsuit\)
אם הפסוק \(P\rightarrow Q\) נכון נאמר שתנאי הכרחי ומספיק לכך ש-\(Q\) יתקיים הוא ש-\(P\) מתקיים (כמובן שזה עובד גם בכיוון ההפוך).
\(\clubsuit\)
לפעמים משתמשים בחיצים כפולים: \(P\Rightarrow Q\) או \(P\Longleftrightarrow Q\), המשמעות המתמטית של החיצים הכפולים זהה למשמעות של המקורית אך בד"כ משתמשים בחץ הכפול "\(\Rightarrow\)" כדי לומר את המילים "מכאן ש-" ולא כדי לומר "אם \(P\) אז \(Q\)" ואילו השימוש בחץ הכפול "\(\Longleftrightarrow\)" בא ליופי או כחלק מכותרת/ ניסוח של משפט ולא סתם שלב בהוכחה.
\(\clubsuit\)
נהוג להקדים את הקשר "לא" לכל קשר אחר (כפי שמקדימים כפל לחיבור בסדר פעולות חשבון).
\(\clubsuit\)
ניתן לכתוב את כל הקשרים באמצעות שימוש בקשרים "וגם" (and) ו-"לא" (not)8ישנה מוסכמה שמבצעים את פעולת השלילה של הקשר "לא": לפני כל קשר אחר, כך למשל בשורה הראשונה לא היה צורך להוסיף סוגריים ולכתוב \(\lnot\left(\left(\lnot P\right)\land\left(\lnot Q\right)\right)\).:\[\begin{align*}
P\lor Q & \equiv\lnot\left(\lnot P\land\lnot Q\right)\\
P\tilde{\lor}Q & \equiv\lnot\left(P\land Q\right)\land\lnot\left(\lnot P\land\lnot Q\right)\\
P\rightarrow Q & \equiv\lnot P\lor Q\equiv\lnot\left(\lnot\left(\lnot P\right)\land\lnot Q\right)\equiv\lnot\left(P\land\lnot Q\right)\\
P\longleftrightarrow Q & \equiv\left(P\land Q\right)\lor\left(\lnot P\land\lnot Q\right)\equiv\lnot\left(P\land\lnot Q\right)\land\lnot\left(\lnot P\land Q\right)
\end{align*}\]ניתן לעשות זאת גם באמצעות קשר יחיד בשם nand(שמקבל ערך שקר רק כאשר שני הפסוקים נכונים), אבל זה כבר מעבר לעניינו של קובץ זה. ישנם בסה"כ \(16\) קשרים בינאריים אפשריים (\(2^{4}\) אפשרויות מפני שישנם \(4\) מקרים ועבור כל אחד מהם ישנם שני ערכי אמת אפשריים), אלו הקשרים הבסיסיים.
נניח שאנו רוצים להוכיח שפסוק \(Q\) נכון, נסמן ב-\(P\) את פסוק ה-"וגם" על כל האקסיומות שלנו9\(P\) היא: אקסיומה1וגם אקסיומה2וגם אקסיומה3וגם... וגם האקסיומה האחרונה. ואז הדרך הקלאסית להוכיח ש-\(Q\) נכון היא לבצע שרשרת של גרירות מ-\(P\) ועד ל-\(Q\) (כלומר שימוש בטענה 1.8כמה פעמים), בתוך זה ניתן לחלק למקרים שונים שעליהם חל הפסוק \(Q\) ולהוכיח בכל אחד מהם בנפרד ש-\(P\) גורר את נכונות \(Q\) כשהוא מצומצמת לכל אחד מן המקרים בנפרד וכך להוכיח ש-\(P\) גורר את \(Q\) בכלל (זוהי הוכחה בדרך חלוקה למקרים).
דרך נוספת היא ההוכחה בדרך השלילה אך לפני שנדבר עליה נצטרך לעסוק קודם בשקילות בין \(P\rightarrow Q\) ל-\(\lnot Q\rightarrow\lnot P\) (מכונה "קונטרה פוזיטיב"), שקילות זו היא בעצם השקילות (במילים) בין "בכל המקרים שבהם \(P\) נכון גם \(Q\) נכון" לבין "האפשרות היחידה שבה \(Q\) אינו נכון10שקול לכך ש-\(\lnot Q=\MKtrue\). היא שגם \(P\) אינו נכון", כעת נוכל להסביר את הרעיון מאחורי הוכחה בדרך השלילה.
מכיוון ש-\(Q\) הוא פסוק עקרון השלישי הנמנע קובע שישנם בדיוק שני מקרים: או ש-\(Q=\MKtrue\) או ש-\(Q=\MKfalse\) (זהו "או" מוציא), לכן אם נראה שהמקרה \(Q=\MKfalse\) אינו אפשרי (או למצער שלא ייתכן ש-\(Q=\MKfalse\) וגם שהאקסיומות שלנו נכונות) הרי שהוכחנו שהמקרה האחר נכון (כלומר \(Q=\MKtrue\) כנדרש). בדרך כלל הוכחה בשלילה עובדת כך: נניח ש-\(Q=\MKfalse\)11זוהי ה"הנחה בשלילה" המפורסמת: נניח בשלילה ש-\(Q=\MKfalse\)., כלומר ש-\(\lnot Q=\MKtrue\), ולאחר שרשרת של גרירות נגלה שהפסוק \(\lnot Q\) (יחד עם האקסיומות שלנו או בלעדיהן) מוביל ל-\(\lnot P\), לאמר "האפשרות היחידה שבה \(Q\) אינו נכון היא שגם \(P\) אינו נכון" וזה שקול לכך ש-"בכל המקרים שבהם \(P\) נכון גם \(Q\) נכון", אבל אנחנו טוענים ש-\(P\) נכון בכל המקרים (הרי אלו האקסיומות שלנו) ומכאן ש-\(Q\) נכון בכל המקרים.
במקרים נדירים נגלה ש-\(\lnot Q\) מוביל ל-\(Q\) (או ל-\(\lnot\left(\lnot Q\right)\) השקול לו), כמעט תמיד הגרירות המובילות מ-\(\lnot Q\) ל-\(Q\) תסתמכנה על \(P\) ולכן אין הבדל גדול בין שני המקרים (עדיין הגענו "רק" לכך שבכל המקרים שבהם \(P\) נכון גם \(Q\) נכון); אולם תאורטית, ייתכן שהגרירות לא תסתמכנה על \(P\) ואז קורה דבר מוזר: הוכחנו בעצם ש-\(Q\) נכון בכל מערכת אקסיומות (!), אישית קשה לי להאמין שקיים פסוק כזה שאיננו טאוטולוגיה (כדוגמת "כל האנשים הם בני אדם") ו/או נכון באופן ריק (כדוגמת "כל האיברים בקבוצה הריקה הם אנשים ג'ינג'ים") ולכן אם הגעתם למצב כזה (שאינו טאוטולוגיה ו/או נכון באופן ריק) אני מציע לבדוק את עצם היותו של \(Q\) פסוק12לדוגמה: נסמן ב-\(Q\) את ה"פסוק": "המשפט הזה אינו נכון" (פרדוקס השקרן). נניח בשלילה ש-\(Q=\MKfalse\) ומכאן שלא נכון לומר ש-\(Q\) אינו נכון (זהו התוכן של \(Q\)), כלומר \(\lnot\left(\lnot Q\right)=\MKtrue\) וזה שקול לכך ש-\(Q=\MKtrue\) בסתירה להנחת השלילה, מכן שהנחת השלילה אינה נכונה ו-\(Q\) נכון.\(\:\)אבל...ניתן היה להניח בשלילה ש-\(Q=\MKtrue\) ומכאן ש-\(Q=\MKfalse\) בסתירה להנחת השלילה ולהסיק ש-\(Q\) אינו נכון, מה קורה כאן? האם יש בעיה בעצם הרעיון שניתן להניח בשלילה?האמת היא שייתכן שכן ואכן יש אסכולות מתמטיות השוללות הוכחה בדרך השלילה (כגון האינטואיציוניזם) אבל נראה לי שפרדוקס השקרן אינו סיבה מספקת לכך: אם נחלק למקרים נגלה שאף אחד משני המקרים (אמת או שקר) אינו אפשרי ולכן א"א לשייך ל-\(Q\) ערך אמת, כלומר הוא אינו פסוק..
3 קבוצות
\(\clubsuit\)
כל עוד לא נלמד קורסים שעוסקים בתורת הקבוצות כנושא מרכזי נתייחס לקבוצה כמושג יסוד13כמו שלא ייתכן שכל הטענות נתמכות ע"י טענות אחרות אלא מוכרחות להיות טענות שהן הראשונות בשרשרת (האקסיומות - טענות היסוד) כך גם חייבים להיות מושגים שא"א להגדיר אותם ע"י מושגים קודמים ואלו נקראים מושגי יסוד., מבחינה אינטואיטיבית קבוצה היא פשוט אוסף14כן, זה מעגלי: מה זה אוסף? -קבוצה, ומהי קבוצה? -אוסף, רבל הייתי חייב לכתוב כאן משהו... של פרטים הנקראים איברי הקבוצה (ייתכן שישנם אין-סוף איברים בקבוצה). הדרך הפשוטה ביותר לתאר קבוצה מסוימת היא לכתוב את איברי הקבוצה בתוך סוגריים מסולסלים, כך: \(\left\{ 1,2,3\right\} \), צורה נוספת היא \(\left\{ x\mid P\left(x\right)\right\} \) או \(\left\{ x:P\left(x\right)\right\} \) כאשר \(P\) הוא פסוק במשתנה \(x\)15כלומר \(P\) אינו פסוק עד שמכניסים לתוכו \(x\) מסוים וזאת מפני שהוא נכון עבור \(x\)-ים מסוימים ואינו נכון עבור אחרים ולכן ערך האמת שלו אינו מוגדר עד שמגדירים את \(x\). - זוהי קבוצת כל ה-\(x\)-ים מצורה מסוימת (במקרה זה לא הגבלנו את הצורה) שעבורם \(P\left(x\right)=\MKtrue\)16לפעמים יהיה בתיאור הקבוצה יותר מפסוק אחד במשתנה \(x\) ואז המוסכמה היא שכל עוד לא נאמר אחרת הפסוקים מקושרים זה לזה ע"י קשר "וגם", כלומר כדי שאיבר "יוכל להיכנס" לקבוצה עליו לקיים את כל הפסוקים..
סימונים:
אם \(a\) הוא איבר של קבוצה \(A\) נסמן \(a\in A\) (קרי \(a\)שייך ל-\(A\))17זהו פסוק., ואם \(a\) אינו איבר של \(A\) נסמן \(a\notin A\) (קרי \(a\)לא שייך ל-\(A\)).
את מספר האיברים בקבוצה סופית18גם למונח קבוצה סופית נתייחס לעת עתה כמושג יסוד, בסיכום של אינפי'2 (בקובץ "קבוצות בנות מנייה וסכומים אינסופיים") מופיעה הגדרה פורמלית.\(A\) נסמן ב-\(\left|A\right|\) ונקרא ל-\(\left|A\right|\) הגודל של \(A\) (או העוצמה של \(A\))19סימון זהה משמש לציון העוצמה של קבוצה אינסופית..
את הקבוצה הריקה (זו שאין בה איברים כלל) נסמן ע"י \(\emptyset:=\left\{ \right\} \).
באינפי' 1נגדיר את המספרים הטבעיים, השלמים, הרציונליים והממשיים:
קבוצת המספרים הטבעיים (לא כולל \(0\)) מסומנת ע"י \(\MKnatural\) (סימון עבור טבעיים כולל \(0\) הוא \(\MKnatural_{0}:=\MKnatural\cup\left\{ 0\right\} \)20זמן רב לא ידעתי אם הסימון הזה מקובל, המצאתי אותו בעצמי ואז איתמר צביק (שלימד אותי את ליניארית2) השתמש בו בהרצאה ללא כל הסבר וכששאלתי אותו אם זה סימון מקובל ענה ”כל הסימונים שלי מקובלים“ (שפטו בעצמכם...) עד שמצאתי אותו בוויקיפדיה האנגלית.).
קבוצת המספרים השלמים מסומנת ב-\(\MKinteger\).
קבוצת המספרים הרציונליים תסומן ע"י \(\MKrational\).
קבוצת המספרים הממשיים תסומן ב-\(\MKreal\).
באלגברה ליניאריתנראה גם את הסימון "\(\MKcomplex\)" עבור המספרים המרוכבים.
4 כמתים
נסמן \(A:=\left\{ 1,2,3\right\} \) המשפט "\(x\) קטן מ-\(4\)" אינו פסוק משום ש-\(x\) אינו מוגדר ולכן אין למשפט ערך אמת מוגדר, לעומת זאת המשפט "לכל \(x\) ששייך ל-\(A\) מתקיים ש-\(x\) קטן מ-\(4\)" הוא פסוק ואפילו מדובר בפסוק אמת; כמו כן המשפט "קיים \(x\) כך ש-\(x\) גדול מ-\(4\)" אינו פסוק (מאותה סיבה) אבל "קיים \(x\) ששייך ל-\(A\) כך ש-\(x\) גדול מ-\(4\)" הוא פסוק (במקרה הזה זהו פסוק שקר).
לכמתים21נקראים כך מפני שהם מכמתים לנו את האיברים שבהם מדובר. "לכל" ו-"קיים" ישנם סימונים מתמטיים, את הכמת "לכל" מסמנים ע"י "\(\forall\)"22האות "A" הפוכה בשביל "All". ואת הכמת "קיים" נסמן ב-"\(\exists\)"23האות "E" הפוכה בשביל "Exists". (ישנו גם סימון עבור "לא קיים": "\(\nexists\)" אבל כמעט שלא משתמשים בו); וכך את הפסוקים שלעיל ניתן לכתוב כך:\[\begin{align*}
& \forall x\in A:x<4\\
& \exists x\in A:x>4
\end{align*}\]
נשים לב שהכמתים הללו הפוכים זה לזה במובן מסוים:\[\begin{align*}
\lnot\left(\forall x\in A:x<4\right) & \Longleftrightarrow\exists x\in A:\lnot\left(x<4\right)\\
\lnot\left(\exists x\in A:x<4\right) & \Longleftrightarrow\forall x\in A:\lnot\left(x<4\right)
\end{align*}\]
\(\clubsuit\)
הסדר בין שני כמתים שונים משנה את משמעות המשפט: הפסוק \(\forall n\in\MKnatural\exists m\in\MKnatural:n<m\) (בעברית: לכל מספר טבעי \(n\) קיים מספר טבעי \(m\) כך ש-\(n\) קטן מ-\(m\).) הוא פסוק אמת ואילו הפסוק \(\exists m\in\MKnatural\forall n\in n:n<m\) (בעברית: קיים מספר טבעי \(m\) כך שלכל מספר טבעי \(n\), \(n\) קטן מ-\(m\).) הוא פסוק שקר. לעומת זאת הסדר בין שני כמתים זהים אינו משנה:\[\begin{align*}
\forall n & \in\MKnatural\forall q\in\MKrational:n\cdot q\in\MKrational\Longleftrightarrow\forall q\in\MKrational\forall n\in\MKnatural:n\cdot q\in\MKrational\\
\exists n & \in\MKnatural\exists m\in\MKinteger:n+m<0\Longleftrightarrow\exists m\in\MKinteger\exists n\in\MKnatural:n+m<0
\end{align*}\]
\(\clubsuit\)
כדי להוכיח שפסוק המתחיל בכמת "לכל" מתקיים נאמר יהי \(x\) בקבוצה המתאימה, נוכיח ש-\(x\) מקיים את הנדרש ומכיוון ש-\(x\) היה שרירותי (הדבר היחיד שידענו עליו הוא שהוא שייך לקבוצה מתאימה) הדבר נכון לכל \(x\) באותה קבוצה24אנחנו נשתמש בשיטה זו גם כדי להקל על ניסוח של הגדרות, יחד עם זאת יש לשים שמבחינה פורמלית האמירה "יהי \(x\) בקבוצה במתאימה" אומרת שאנחנו לוקחים \(x\)מסוים מהקבוצה.; כדי להוכיח פסוק "קיים" יש שתי דרכים: ניתן להצביע על \(x\) בקבוצה המתאימה שמקיים את הדרוש (הוכחה קונסטרוקטיבית) אך ניתן גם להראות שקיים \(x\) בקבוצה המתאימה המקיים את הנדרש גם מבלי להצביע עליו (הוכחה שאינה קונסטרוקטבית), הדוגמה הקלאסית להוכחה בצורה השנייה היא הוכחת התכנסות של סדרה באמצעות תנאי קושי להתכנסות (אנחנו מראים שקיים גבול אך איננו יודעים מהו).
5 יחסים בין קבוצות
הגדרה 5.1. נאמר ששתי קבוצות \(A\) ו-\(B\)זרות זו לזו אם לא קיים איבר ששייך לשתיהן (כלומר \(\nexists a\in A:a\in B\land\nexists b\in B:b\in B\)), וזה שקול לכך ש-\(A\cap B=\emptyset\).
הגדרה 5.2. נאמר שקבוצה \(A\)מוכלת בקבוצה \(B\) (וגם ש-\(A\) היא תת-קבוצה של \(B\)) ונסמן \(A\subseteq B\), אם כל איבר ב-\(A\) הוא גם איבר ב-\(B\) (כלומר \(\forall a\in A:a\in B\)).
טענה 5.3. הכלה היא יחס סדר חלש25נראה את המושג הזה בפרק על יחסים בינאריים., כלומר מתקיימים שלושת הפסוקים הבאים:
רפלקסיביות: לכל קבוצה \(A\) מתקיים \(A\subseteq A\).
אנטי-סימטריות: לכל שתי קבוצות \(A\) ו-\(B\), אם \(A\subseteq B\) וגם \(B\subseteq A\) אז \(A=B\).
טרנזיטיביות: לכל שלוש קבוצות \(A\), \(B\) ו-\(C\), אם \(A\subseteq B\) וגם \(B\subseteq C\) אז \(A\subseteq C\).
\(\clubsuit\)
הכלה היא יחס סדר חלש26גם את המושג הזה נראה בפרק על יחסים בינאריים., כלומר קיימות שתי קבוצות \(A\) ו-\(B\) כך ש-\(A\nsubseteq B\) וגם \(B\nsubseteq A\) (למשל הקבוצות \(\left\{ 1\right\} \) ו-\(\left\{ 0\right\} \)).
\(\clubsuit\)
הסימון "\(\subset\)" הוא סימון דו משמעי, יש משתמשים בו כפי שהגדרנו לעיל ויש המשתמשים בו כדי לציין הכלה רגילה (לא הכלה ממש) וכדי לציין הכלה ממש משתמשים בסימון "\(\subsetneq\)", אני בחרתי להגדיר כפי שהגדרתי ע"מ לשמור על היופי (שלילה היא תמיד דבר מכוער) וכדי להיות עקבי עם הסימונים "\(\leq\)" ו-"\(<\)"; על כל פנים המשמעות של הסימנים "\(\subseteq\)" ו-"\(\subsetneq\)" הן חד משמעיות עבור כולם.
\(\clubsuit\)
מכאן נובעת טענה פשוטה שלא קיימות שתי קבוצות \(A\) ו-\(B\) כך ש-\(A\subset B\) וגם \(B\subset A\).
\(\clubsuit\)
כלומר אין משמעות לכתיבה של איבר מסוים פעמיים בתוך הסוגריים המסולסלים וגם אין משמעות לסדר שבו כותבים את האיברים בתוך הסוגריים.
\(\clubsuit\)
מהגדרה זו נובע שקיימת לכל היותר קבוצה אחת ריקה (שאין בה איברים), אנחנו נניח שהיא קיימת ונסמן אותה ב-"\(\emptyset\)".
הגדרה 5.4. נאמר שקבוצה \(A\)מוכלת ממש בקבוצה \(B\) (וגם ש-\(A\) היא תת-קבוצה ממש של \(B\)) ונסמן \(A\subset B\), אם כל איבר ב-\(A\) הוא גם איבר ב-\(B\) (כלומר \(\forall a\in A:a\in B\)) ובנוסף קיים איבר ב-\(B\) שאינו איבר ב-\(A\) (כלומר \(\exists b\in B:b\notin A\)).
טענה 5.5. הכלה ממש היא יחס סדר חזק27גם את המושג הזה נראה בפרק על יחסים בינאריים., כלומר מתקיימים שני הפסוקים הבאים:
אנטי-רפלקסיביות: לכל קבוצה \(A\) לא מתקיים \(A\subset A\).
טרנזיטיביות: לכל שלוש קבוצות \(A\), \(B\) ו-\(C\), אם \(A\subset B\) וגם \(B\subset C\) אז \(A\subset C\)28למעשה הדבר נכון גם אם \(A\subseteq B\) או \(B\subseteq C\) (אך לא שניהם יחד)..
הגדרה 5.6. נאמר ששתי קבוצות \(A\) ו-\(B\) הן שוות זו לזו (הן אותה קבוצה) אם יש בהן אותן איברים (רוצה לומר שהדבר היחיד שמאפיין קבוצה הוא אילו איברים שייכים לה ואילו לא), וזה שקול לכך ש-\(A\subseteq B\) וגם \(B\subseteq A\).
6 פעולות על קבוצות
6.1 תכונות של פעולות
\(\clubsuit\)
התכונות שלהלן הן תכונות כלליות של פעולות בינאריות, לאו דווקא פעולות על קבוצות29למען האמת הנושא הזה היה צריך להופיע לאחר שנגדיר מהי פעולה אבל הצורך דוחק בנו להכיר את התכונות כבר כעת..
הגדרה. תהא \(\oplus\) פעולה בינארית על קבוצה \(A\) (כלומר לכל \(a,b\in A\) הביטוי "\(a\oplus b\)" מוגדר).
נאמר ש-\(\oplus\) מקיימת את חוק החילוף (קומוטטיבית) אם לכל \(a,b\in A\) מתקיים \(a\oplus b=b\oplus a\).
נאמר ש-\(\oplus\) מקיימת את חוק הקיבוץ (אסוציאטיבית) אם לכל \(a,b,c\in A\) מתקיים \(\left(a\oplus b\right)\oplus c=a\oplus\left(b\oplus c\right)\).
תהא \(\odot\) גם היא פעולה מ-\(A\), נאמר ש-\(\odot\) מקיימת את חוק הפילוג (דיסטריבוטיבית) ביחס לפעולה \(\oplus\) אם לכל \(a,b,c\in A\) מתקיים \(a\odot\left(b\oplus c\right)=\left(a\odot b\right)\oplus\left(a\odot c\right)\).
6.2 פעולות בסיסיות
הגדרה 6.1. חיתוך קבוצות חיתוך קבוצות הוא פעולה בינארית המחזירה לכל שתי קבוצות \(A\) ו-\(B\) את הקבוצה \(A\cap B\) (קרי: \(A\) חיתוך עם \(B\) או: \(A\) חיתוך \(B\)) המוגדרת ע"י:\[
A\cap B:=\left\{ x\mid x\in A\land x\in B\right\}
\]
הגדרה 6.2. איחוד קבוצות איחוד קבוצות הוא פעולה בינארית המחזירה לכל שתי קבוצות \(A\) ו-\(B\) את הקבוצה \(A\cup B\) (קרי: \(A\) איחוד עם \(B\) או \(A\) איחוד \(B\)) המוגדרת ע"י:\[
A\cup B:=\left\{ x\mid x\in A\lor x\in B\right\}
\]
\(\clubsuit\)
כאשר מדובר באיחוד של קבוצות זרות יש המציינים זאת ע"י החלפת הסימון "\(\cup\)", ב-"\(\uplus\)", ב-"\(\MKcupdot\)" או ב-"\(\sqcup\)", כך: \(A\uplus B\), \(A\MKcupdot B\) ו-\(A\sqcup B\).
\(\clubsuit\)
ניתן להסיק מכאן שבכל מקרה מתקיים \(\left|A\cup B\right|=\left|A\right|+\left|B\right|-\left|A\cap B\right|\) שהרי הקבוצות \(A\) ו-\(B\setminus A\) זרות זו לזו ובנוסף מתקיים \(A\cup\left(B\setminus A\right)=A\cup B\) ו-\(B\setminus A=B\setminus\left(A\cap B\right)\) ואז:\[
\left|A\cup B\right|=\left|A\cup\left(B\setminus A\right)\right|=\left|A\right|+\left|B\setminus A\right|=\left|A\right|+\left|B\setminus\left(A\cap B\right)\right|
\]והרי גם \(B\setminus\left(A\cap B\right)\) ו-\(A\cap B\) זרות זו לזו ולכן:\[
\left|B\right|=\left|B\setminus\left(A\cap B\right)\right|+\left|A\cap B\right|
\]\[
\Rightarrow\left|B\setminus\left(A\cap B\right)\right|=\left|B\right|-\left|A\cap B\right|
\]\[
\Rightarrow\left|A\cup B\right|=\left|A\right|+\left|B\right|-\left|A\cap B\right|
\]זהו עקרון ההכלה וההדחה שאותו נראה בקובץ שיעסוק בקומבינטוריקה.
\(\clubsuit\)
המשפט נובע ישירות מהחילוף, הקיבוץ והפילוג של הקשרים "וגם" ו-"או" (4השקילויות האחרונות בטענה הראשונה), ראו פירוט אודות הקשר בין האיחוד והחיתוך לקשרים "או" ו-"וגם" בהערה על חוקי דה-מורגן (משפט 5.12).
\(\clubsuit\)
נשים לב לדמיון שבין חוקי דה-מורגן לשקילויות \(\lnot\left(P\land Q\right)\Longleftrightarrow\lnot P\lor\lnot Q\) (דומה לחוק הראשון) ו-\(\lnot\left(P\lor Q\right)\Longleftrightarrow\lnot P\land\lnot Q\) (דומה לחוק השני), הדמיון הזה אינו מקרי: מה הקשר בין "\(\land\)" ל-"\(\cap\)", בין "\(\lor\)" ל-"\(\cup\)" ובין "\(^{c}\)" ל-"\(\lnot\)"? כמובן:\[\begin{align*}
A\cap B & :=\left\{ x\mid x\in A\ \land\ x\in B\right\} \\
A\cup B & :=\left\{ x\mid x\in A\ \lor\ x\in B\right\} \\
A^{c} & :=\left\{ x\in U\mid\lnot\left(x\in A\right)\right\}
\end{align*}\]אני חושב שזוהי גם הסיבה לדמיון בין הסמלים המייצגים את הקשרים והפעולות. ניתן למצוא אנלוגיה גם בין הגרירה להכלה וממילא גם בין השקילות של שני פסוקים (אם ורק אם - גרירה דו כיוונית) לשוויון בין שתי קבוצות (הכלה דו-כיוונית).
\(\clubsuit\)
טענה זו וטענות נוספות הקושרות בין קבוצת החזקה לתכונות של חזקות הן שנתנו לקבוצת החזקה את שמה.
טענה 6.3. תהיינה \(A\) ו-\(B\) קבוצות סופיות, אם \(A\) ו-\(B\) זרות אז \(\left|A\cup B\right|=\left|A\right|+\left|B\right|\)30ניתן להסיק מכאן באינדוקציה גם ליותר משתי קבוצות. (אחרת מתקיים \(\left|A\cup B\right|\leq\left|A\right|+\left|B\right|\)).
משפט 6.4. איחוד וחיתוך הם קומוטטיביים ואסוציאטיביים, בנוסף, הם גם דיסטריבוטיביים זה ביחס לזה; כלומר לכל שלוש קבוצות \(A\), \(B\) ו-\(C\) מתקיים:
הגדרה 6.5. חיסור קבוצות חיסור קבוצות הוא פעולה בינארית המחזירה לכל שתי קבוצות \(A\) ו-\(B\) את הקבוצה \(A\setminus B\) (קרי: \(A\) פחות \(B\)) המוגדרת ע"י:\[
A\setminus B:=\left\{ x\in A\mid x\notin B\right\}
\]
טענה 6.6. תהיינה \(A\) ו-\(B\) שתי קבוצות סופיות, אם \(B\subseteq A\) אז \(\left|A\setminus B\right|=\left|A\right|-\left|B\right|\).
טענה 6.7. לכל שלוש קבוצות \(A\), \(B\) ו-\(C\) מתקיימים שני הפסוקים הבאים:
הגדרה 6.8. תהא \(U\) קבוצה ותהא \(A\subseteq U\) תת-קבוצה שלה, המשלים של \(A\) (ביחס ל-\(U\)) הוא הקבוצה \(U\setminus A\) שנהוג לסמנה ע"י \(A^{c}\) או ב-\(\overline{A}\).
משפט 6.9. חוקי דה-מורגן31ערך בוויקיפדיה: אוגוסטוס דה מורגן. תהא \(U\) קבוצה ותהיינה \(A,B\subseteq U\), מתקיים:
\(\left(A\cap B\right)^{c}=A^{c}\cup B^{c}\)
\(\left(A\cup B\right)^{c}=A^{c}\cap B^{c}\)
הגדרה 6.10. קבוצת החזקה תהא \(A\) קבוצה, קבוצת החזקה של \(A\) (מסומנת ב-\(P\left(A\right)\)) היא קבוצת כל תתי-הקבוצות של \(A\):\[
P\left(A\right):=\left\{ X\mid X\subseteq A\right\}
\]
טענה 6.11. תהא \(A\) קבוצה סופית, מתקיים \(\left|P\left(A\right)\right|=2^{\left|A\right|}\).
6.3 המכפלה הקרטזית
\(\clubsuit\)
סדרה סופית היא כעין קבוצה אלא שבה הסדר משנה את זהותה של הסדרה ומסיבה זו יכול איבר להופיע בה יותר מפעם אחת, הדרך הפשוטה ביותר לתאר סדרה מסוימת היא לכתוב את איברי הסדרה בתוך סוגריים מעוגלים, כך: \(\left(1,2,3\right)\).
\(\clubsuit\)
נשים לב שמבחינה פורמלית המכפלה הקרטזית אינה אסוציאטיבית:\[\begin{align*}
\left(A\times B\right)\times C & =\left\{ \left({\color{red}\left(a,b\right)},c\right)\mid a\in A,\ b\in B,\ c\in C\right\} \\
& {\color{red}\neq}\left\{ \left(a,{\color{red}\left(b,c\right)}\right)\mid a\in A,\ b\in B,\ c\in C\right\} =A\times\left(B\times C\right)
\end{align*}\]למרות זאת, מכיוון ש-\(\left(A\times B\right)\times C\) ו-\(A\times\left(B\times C\right)\) איזומורפיות שתיהן ל-\(\left\{ \left(a,b,c\right)\mid a\in A,\ b\in B,\ c\in C\right\} \) (ולכן איזומורפיות זו לזו) מקובל להתייחס אליה כפעולה אסוציאטיבית שמחזירה קבוצת סדרות באורך מספר הקבוצות שבמכפלה הקרטזית, מדובר כמובן בסדרות שכל איבר בהן הוא איבר בקבוצה המתאימה (לפי הסדר של המכפלה32גם לאחר הסכמה זו המכפלה הקרטזית אינה קומוטטיבית.) ולא סדרה הכוללת איברים, כך:\[
A_{1}\times A_{2}\times\ldots\times A_{n}:=\left\{ \left(a_{1},a_{2},\ldots,a_{n}\right)\mid\forall n\geq i\in\MKnatural:a_{i}\in A_{i}\right\}
\]
\(\clubsuit\)
הסכמה זו מאפשרת לנו להגדיר (לכל \(n\in\MKnatural\) ולכל קבוצה \(A\))33סימון זה גם הוא סימון מקובל ובתחילת התואר נפגוש אותו בעיקר בקורסי אלגברה ליניארית.:\[
A^{n}:=\underset{\text{n פעמים}}{\underbrace{A\times A\times\ldots\times A}}=\left\{ \left(a_{1},a_{2},\ldots,a_{n}\right)\mid\forall n\geq i\in\MKnatural:a_{i}\in A\right\}
\]נשים לב לכך ש-\(A^{1}\) איזומורפית ל-\(A\) ולכן מקובל להתייחס אליה כך.
\(\clubsuit\)
אם \(A\) ו/או \(B\) ריקות אז מהגדרה נובע ש-\(A\times B=\emptyset\).
\(\clubsuit\)
טענה זו היא שנתנה למכפלה הקרטזית את שמה.
\(\clubsuit\)
לסיכום ניתן לכתוב כמה מהטענות האחרונות תחת הכותרת "חוקים חשבוניים": תהיינה \(A\) ו-\(B\) שתי קבוצות סופיות,
אם \(A\) ו-\(B\) זרות אז \(\left|A\cup B\right|=\left|A\right|+\left|B\right|\).
אם \(B\subseteq A\) אז \(\left|A\setminus B\right|=\left|A\right|-\left|B\right|\).
מתקיים \(\left|A\times B\right|=\left|A\right|\cdot\left|B\right|\).
מתקיים \(\left|P\left(A\right)\right|=2^{\left|A\right|}\).
הגדרה 6.12. מכפלה קרטזית34על שמו של רנה דקארט. מכפלה קרטזית היא פעולה בינארית המחזירה לכל שתי קבוצות \(A\) ו-\(B\) את קבוצת כל הזוגות הסדורים שהאיבר הראשון שלהם שייך ל-\(A\) והשני שייך ל-\(B\), נסמן את המכפלה הקרטזית של \(A\) ו-\(B\) ב-\(A\times B\) (קרי: \(A\) קרוס \(B\)):\[
A\times B:=\left\{ \left(a,b\right)\mid a\in A,\ b\in B\right\}
\]
טענה 6.13. לכל שתי קבוצות סופיות \(A\) ו-\(B\) מתקיים \(\left|A\times B\right|=\left|A\right|\cdot\left|B\right|\)35ניתן להסיק מכאן באינדוקציה גם ליותר משתי קבוצות..
7 יחסים בינאריים
7.1 התחלה
הגדרה 7.1. תהיינה \(A\) ו-\(B\) קבוצות, תת-קבוצה \(R\subseteq A\times B\) נקראת יחס בינארי מ-\(A\) ל-\(B\), אם \(A=B\) אז נאמר שזהו יחס על\(A\). אם \(\left(a,b\right)\in R\) אז נאמר ש-\(a\)מתייחס ל-\(b\) ונסמן \(aRb\).
\(\clubsuit\)
הרעיון מאחורי ההגדרה הזו הוא לשמור על פורמליות, זו הדרך הקלה ביותר להגדיר יחסים (כגון: "קטן מ-" ושוויון) כפי שאנחנו מכירים אותם מבלי להזדקק לתוכן של היחס, כך למשל יחס השוויון על \(\MKreal\) הוא פשוט \("=":=\left\{ \left(x,x\right)\in\MKreal^{2}\right\} \) והיחס "קטן מ-" על הקבוצה \(\left\{ 1,2,3,4\right\} \) הוא:\[
\left\{ \left(1,2\right),\left(1,3\right),\left(1,4\right),\left(2,3\right),\left(2,4\right),\left(3,4\right)\right\}
\]מלבד הרווח שבפורמליות לדעתי האישית זוהי צורה נוראית להגדיר יחסים, אני מוכן רק לומר שהקבוצות הללו איזומורפיות ליחסים אותן הן מתיימרות לייצג.
\(\clubsuit\)
ניתן לייצג יחס \(R\) על קבוצה \(A\) ע"י ייצוג איברי \(A\) כנקודות ומתיחת חיצים בין האיברים המקיימים את היחס \(R\) (כאשר החץ יוצא מהאיבר השמאלי בזוג הסדור ונכנס לימני), בהמשך הקורס מתמטיקה בדידה נראה שלייצוג כזה קוראים "גרף מכוון".
\(\clubsuit\)
היחסים זרות, הכלה, הכלה ממש ושוויון שראינו בפרק הקודם הם יחסים בינאריים על קבוצות36לא כתבתי כאן "קבוצת כל הקבוצות" מפני שזו מעוררת בעיות לוגיות, ראו את הפרדוקס של קנטור בוויקיפדיה..
\(\clubsuit\)
הגדרה זו דומה מאד להגדרת הרכבה של פונקציות (בהמשך) ולמעשה היא הכללה שלה שכן כל פונקציה היא יחס אך לא כל יחס הוא פונקציה.
הגדרה 7.2. תהיינה \(A\), \(B\) ו-\(C\) קבוצות ויהיו \(R\subseteq A\times B\) ו-\(S\subseteq B\times C\) יחסים, נגדיר את יחס ההרכבה\(S\circ R\) ע"י:\[
S\circ R:=\left\{ \left(a,c\right)\in A\times C\mid\exists b\in B:\left(a,b\right)\in R\land\left(b,c\right)\in S\right\}
\]
הגדרה 7.3. תהא \(A\) קבוצה, היחס הריק על \(A\) הוא \(\emptyset\), יחס הזהות על \(A\) הוא \(\left\{ \left(a,a\right)\mid a\in A\right\} \) והיחס המלא על \(A\) הוא \(A^{2}\).
תהא \(A\) קבוצה ויהיו \(R\) ו-\(S\) יחסים על \(A\).
הגדרה 7.4. תכונות של יחסים בינאריים
נאמר ש-\(R\)רפלקסיבי אם לכל \(a\in A\) מתקיים \(\left(a,a\right)\in R\).
נאמר ש-\(R\)אנטי-רפלקסיבי אם לכל \(a\in A\) מתקיים \(\left(a,a\right)\notin R\).
נאמר ש-\(R\)סימטרי אם לכל \(a,b\in A\) המקיימים \(\left(a,b\right)\in R\) מתקיים \(\left(b,a\right)\in R\).
נאמר ש-\(R\)אנטי-סימטרי אם לכל \(a,b\in A\) המקיימים \(\left(a,b\right)\in R\) וגם \(\left(b,a\right)\in R\) מתקיים \(a=b\).
נאמר ש-\(R\)טרנזיטיבי אם לכל \(a,b,c\in A\) המקיימים \(\left(a,b\right)\in R\) וגם \(\left(b,c\right)\in R\) מתקיים \(\left(a,c\right)\in R\).
טענה 7.5. \(\:\)
היחס הריק על \(A\) הוא אנטי-רפלקסיבי, סימטרי, אנטי-סימטרי וטרנזיטיבי; היחס הריק אינו רפלקסיבי אם"ם \(A\neq\emptyset\).
בסעיפים הבאים נניח ש-\(A\neq\emptyset\) מפני שאחרת קיים רק יחס אחד על \(A\) והוא היחס הריק.
יחס הזהות על \(A\) הוא רפלקסיבי, סימטרי, אנטי-סימטרי וטרנזיטיבי; יחס הזהות אינו אנטי-רפלקסיבי.
היחס המלא על \(A\) הוא רפלקסיבי, סימטרי וטרנזיטיבי; היחס המלא אינו אנטי-רפלקסיבי; היחס המלא אינו אנטי-סימטרי אם"ם \(\left|A\right|\geq2\) (או ש-\(A\) אינסופית).
טענה 7.6. מתקיימים כל הפסוקים הבאים:
אם \(R\) ו-\(S\) הם יחסים סימטריים אז \(R\setminus S\) הוא יחס סימטרי.
אם \(R\) הוא יחס אנטי-סימטרי אז \(R\setminus S\) הוא יחס אנטי-סימטרי.
אם \(R\) ו-\(S\) הם יחסים אנטי-סימטריים אז \(R\cap S\) הוא יחס אנטי-סימטרי.
אם \(R\) ו-\(S\) הם יחסים טרנזיטיביים אז \(R\cap S\) הוא יחס טרנזיטיבי.
אם \(R\) ו-\(S\) הם יחסים רפלקסיביים אז \(S\circ R\) הוא יחס רפלקסיבי.
אם \(R=R\circ R\) אז \(R\) הוא יחס טרנזיטיבי.
טענה 7.7. \(R\) הוא יחס סימטרי ואנטי-סימטרי אם"ם הוא מוכל ביחס הזהות.
7.2 יחסי שקילות
הגדרה 7.8. נאמר ש-\(R\) הוא יחס שקילות אם \(R\) רפלקסיבי, סימטרי וטרנזיטיבי.
הגדרה 7.9. קבוצה של קבוצות לא ריקות, זרות זו לזו שאיחודן הוא \(A\) נקראת חלוקה של \(A\)37מהגדרה לא קיימת חלוקה של הקבוצה הריקה., כלומר \(S:=\left\{ A_{1},A_{2},\ldots,A_{n}\right\} \)38יכולה להיות חלוקה המחלקת את \(A\) לאינסוף קבוצות ואז הדרישות מהחלוקה הן:
אין בחלוקה קבוצה ריקה
כל הקבוצות בחלוקה זרות זו לזו
האיחוד של כל הקבוצות הוא \(A\)
היא חלוקה של
\(A_{i}\neq\emptyset\) לכל \(n\geq i\in\MKnatural\).
\(A_{i}\cap A_{j}=\emptyset\)לכל \(n\geq i,j\in\MKnatural\) השונים זה מזה.
\(A_{1}\cup A_{2}\cup\ldots\cup A_{n}=A\).
\(A\) אם היא מקיימת את שלושת התנאים הבאים:
הגדרה 7.10. נניח ש-\(R\) הוא יחס שקילות, לכל \(a\in A\) נגדיר את מחלקת השקילות של \(a\) (ע"פ \(R\)) להיות קבוצת כל האיברים ב-\(A\) שמתייחסים ל-\(a\)39או ש-\(a\) מתייחס אליהם, ביחס שקילות זה היינו הך., כך:\[
\overline{a}:=\left[a\right]_{R}:=\left\{ b\in A\mid\left(a,b\right)\in R\right\}
\]קבוצת כל מחלקות השקילות נקראת החלוקה40ראו בטענה הבאה שאכן מדובר בחלוקה. המושרת ע"י \(R\) וגם קבוצת המנה ונהוג לסמנה ב-\(A/R\).
סימון:
בד"כ נסמן את מחלקות השקילות ע"י נציגים, כלומר ניקח ממחלקת השקילות איבר \(a\) ונסמן אותה ע"י מחלקת השקילות שלו -\(\left[a\right]_{R}\), דרך זו עובדת מפני שאם שני איברים שייכים לאותה מחלקת שקילות אז כמובן שמחלקות השקילות שלהם זהות (או: אם \(b\in\left[a\right]_{R}\) אז \(\left[b\right]_{R}=\left[a\right]_{R}\)).
\(\clubsuit\)
זוהי דרך קצרה יותר לומר שחלוקת \(a\) ו-\(b\) (בנפרד) ב-\(n\) תיתן את אותה שארית (לא הגדרנו מהי שארית).
\(\clubsuit\)
כמובן שיחס השקילות המודולרי, כשמו כן הוא - יחס שקילות.
טענה 7.11. כל קבוצת מחלקות שקילות של יחס שקילות על \(A\) היא חלוקה של \(A\) וכל חלוקה של \(A\) היא קבוצת מחלקות שקילות של יחס שקילות כלשהו על \(A\).
הגדרה 7.12. יחס החלוקה יהיו \(a,b\in\MKinteger\), נאמר ש-\(a\)מחלק את \(b\) (או ש-\(b\) הוא כפולה של \(a\)) ונסמן \(a\mid b\) אם קיים \(q\in\MKinteger\) כך ש-\(b=a\cdot q\).
הגדרה 7.13. יחס השקילות המודולרי יהי \(n\in\MKnatural\) ויהיו \(a,b\in\MKinteger\), נאמר ש-\(a\)שקול ל-\(b\)מודולו\(n\) (ונכתוב \(a\equiv b\mod n\)) אם \(n\mid a-b\).
7.3 יחסי סדר
הגדרה 7.14. יחס סדר חלש נאמר ש-\(R\) הוא יחס סדר חלש אם הוא טרנזיטיבי, אנטי-סימטרי ורפלקסיבי.
הגדרה 7.15. יחס סדר חזק נאמר ש-\(R\) הוא יחס סדר חזק אם הוא טרנזיטיבי ואנטי-רפלקסיבי.
\(\clubsuit\)
מהטרנזיטיביות והאנטי-רפלקסיביות יחד נובע שלכל \(a,b\in A\) לא מתקיים \(aRb\) וגם \(bRa\) אלא לכל היותר אחד מן השניים מתקיים.
\(\clubsuit\)
נשים לב לכך שאם \(R\) הוא יחס סדר חלקי ייתכן שישנם יותר מאיבר אחד מינימלי ואיבר אחד מקסימלי.
\(\clubsuit\)
הזכרנו שניתן לייצג את \(R\) ע"י ייצוג איברי \(A\) כנקודות ומתיחת חיצים בין האיברים המקיימים את היחס \(R\) (כאשר החץ יוצא מהאיבר השמאלי בזוג הסדור ונכנס לימני); ביחס סדר ה"ציור" הזה נראה כמו כמה שרשראות (אחת אם מדובר ביחס סדר מלא), הבעיה היא שישנם חיצים רבים שהטרנזיטיביות מייתרת אותם, זוהי המוטיבציה להגדרה הבאה.
\(\clubsuit\)
דיאגרמת הסה היא ציור כנ"ל שבו מותחים חץ בין שני איברים במקיימים את יחס הסדר ובתנאי שהם זוג לא מיותר.
נניח ש-\(R\) הוא יחס סדר (חלש או חזק).
הגדרה 7.16. נאמר ש-\(R\) הוא יחס סדר מלא41נקרא גם יחס סדר ליניארי או יחס סדר קווי. אם לכל \(a,b\in A\) מתקיים \(aRb\) ו/או \(bRa\) ו/או \(a=b\), אחרת נאמר שהוא יחס סדר חלקי.
הגדרה 7.17. נאמר שאיבר \(a\in A\) הוא איבר מינימלי אם לא קיים \(b\in A\) כך שמתקיים \(bRa\), כמו כן נאמר ש-\(a\) הוא איבר מקסימלי אם לא קיים \(b\in B\) כך ש-\(aRb\).
\(\:\)
הגדרה 7.18. נאמר ששני איברים שונים זה מזה \(a,b\in A\) המקיימים \(aRb\) הם זוג לא מיותר אם לכל \(c\in A\) השונה מ-\(a\) ו-\(b\) לא מתקיים \(aRcRb\).
8 פונקציות
8.1 התחלה
הגדרה 8.1. פונקציה (או העתקה) \(f\) מקבוצה \(A\) לקבוצה \(B\) (מסמנים \(f:A\rightarrow B\)) היא התאמה בין איברי \(A\) ל-\(B\) כך שלכל איבר \(a\in A\) קיים איבר יחיד \(b\in B\) המותאם לו, במילים אחרות פונקציה היא יחס מ-\(A\) ל-\(B\) המקיים את תכונת החד-ערכיות: לכל שני זוגות \(\left(a,b\right)\) ו-\(\left(a,b'\right)\) ביחס מתקיים \(b=b'\).
בסימונים הנ"ל, \(A\) נקראת תחום ההגדרה של הפונקציה \(f\) ואילו \(B\) נקראת הטווח של הפונקציה \(f\).
לכל \(a\in A\) נסמן ב-\(f\left(a\right)\) את האיבר ב-\(B\) ש-\(f\) מתאימה ל-\(a\) וכך \(a\) יהיה מקור של \(f\left(a\right)\) ו-\(f\left(a\right)\) הוא התמונה של \(a\).
הקבוצה \(\text{Graph}f:=\left\{ \left(x,f\left(x\right)\right)\in A\times B\mid x\in A\right\} \) (שהיא בעצם הפונקציה עצמה) נקראת גם גרף הפונקציה.
\(\clubsuit\)
פונקציות מאופיינות ע"פ שלושה דברים:
התחום של הפונקציה - קבוצת האיברים שממנה מגיעה ה"קלט" ל"מכונה".
הטווח של הפונקציה - קבוצת האיברים שיכולה ה"מכונה" להחזיר כ"פלט".
כלל ההעתקה של הפונקציה - קובע עבור כל "קלט" איזה "פלט" תחזיר המכונה.
סימון:
מסמנים את קבוצת הפונקציות מ-\(A\) ל-\(B\) ע"י \(B^{A}:=\left\{ f\mid f:A\rightarrow B\right\} \).
\(\clubsuit\)
לסימון יש קשר לחזקה: אם \(A\) ו-\(B\) סופיות אז \(\left|B^{A}\right|=\left|B\right|^{\left|A\right|}\) (לכל איבר ב-\(A\) ישנן \(\left|B\right|\) אפשרויות לאן "תשלח" אותו הפונקציה), זהו גם סימן טוב לזכור את הסימון.
\(\clubsuit\)
נשים לב: הגדרת השוויון הזו לא התייחסה לטווח באופן מפורש ואכן שינוי הטווח של פונקציה אינו משנה את זהותה אלא אם הטווח החדש אינו מכיל את התמונה של הפונקציה (התמונה תוגדר בשורה הבאה).
\(\clubsuit\)
אם \(C\) סופית אז מהגדרה גם \(f\left(C\right)\) סופית ומתקיים \(\left|f\left(C\right)\right|\leq\left|C\right|\).
\(\clubsuit\)
עבור \(A\) מתקיים \(f\left(A\right)=\MKim f\) (נזכור ש-\(A\subseteq A\)).
\(\clubsuit\)
מקור מוגדר לכל תת-קבוצה של הטווח (ולאו דווקא עבור תתי-קבוצות של התמונה), לכן זה שיש לקבוצה מקור שאינו הקבוצה הריקה עדיין לא אומר שכל איבר בה הוא תמונה של איבר בתחום.
\(\clubsuit\)
סעיף1אינו נכון עבור חיתוך וסעיף2אינו נכון עבור איחוד.
הגדרה 8.2. פונקציית הזהות על קבוצה \(A\) היא הפונקציה \(\MKid_{A}:A\rightarrow A\) המוגדרת ע"י \(\MKid_{A}\left(x\right):=x\) (לכל \(x\in A\)).
הגדרה 8.3. תהא \(f:A\rightarrow A\) פונקציה מקבוצה \(A\) אל עצמה, איבר \(a\in A\) יקרא נקודת שבת של \(f\) אם \(f\left(a\right)=a\).
תהא \(f:A\rightarrow B\) פונקציה מקבוצה \(A\) לקבוצה \(B\).
הגדרה 8.4. תהא \(g:C\rightarrow D\), נאמר ש-\(f=g\) אם \(A=C\) ולכל \(x\in A=C\) מתקיים \(f\left(x\right)=g\left(x\right)\).
הגדרה 8.5. נגדיר את התמונה של \(f\) כך: \(\MKim f:=\left\{ y\in B\mid\exists x\in A:f\left(x\right)=y\right\} =\left\{ f\left(x\right):x\in A\right\} \).
הגדרה 8.6. נגדיר את התמונה של תת-קבוצה\(C\subseteq A\) כך: \(f\left(C\right):=\left\{ y\in B\mid\exists x\in C:f\left(x\right)=y\right\} =\left\{ f\left(x\right):x\in C\right\} \).
הגדרה 8.7. נגדיר את המקור של תת-קבוצה\(D\subseteq B\) כך: \(f^{-1}\left(D\right):=\left\{ x\in A\mid f\left(x\right)\in D\right\} \).
טענה 8.8. תהיינה \(A\) ו-\(B\) שתי קבוצות, תהא \(f:A\rightarrow B\) פונקציה ותהיינה \(C\subseteq A\) ו-\(D\subseteq B\) תתי-קבוצות, מתקיים:\[
f\left(C\right)\cap D=f\left(C\cap f^{-1}\left(D\right)\right)
\]
טענה 8.9. תהיינה \(A\) ו-\(B\) שתי קבוצות, תהא \(f:A\rightarrow B\) פונקציה ותהיינה \(C_{1},C_{2}\subseteq A\) ו-\(D_{1},D_{2}\subseteq B\) תתי-קבוצות, מתקיימים חמשת הפסוקים הבאים:
אם \(C_{1}\subseteq C_{2}\) אז \(f\left(C_{1}\right)\subseteq f\left(C_{2}\right)\).
אם \(D_{1}\subseteq D_{2}\) אז \(f^{-1}\left(D_{1}\right)\subseteq f^{-1}\left(D_{2}\right)\).
8.2 חד-חד-ערכיות, על, הרכבה והפיכות
הגדרה 8.10. נאמר ש-\(f\) היא על \(B\)42התכונה "על" היא תכונה של פונקציה ביחס לקבוצה, וזאת משום שאם נגדיר אותה כתכונה של הפונקציה בלבד נקבל סתירה; לדוגמה: תהא \(f:\MKreal\rightarrow\MKreal\) פונקציה המוגדרת ע"י \(f\left(x\right)=x^{2}\) ותהא \(g:\MKreal\rightarrow\left[0,\infty\right)\) המוגדרת ע"י \(g\left(x\right)=f\left(x\right)\), ע"פ הגדרת שוויון בין פונקציות מתקיים \(f=g\) אך לא ייתכן שהפונקציה היא גם "על" וגם "לא על", לכן נאמר ש-\(f\) היא על \(\left[0,\infty\right)\) אך אינה על \(\MKreal\). למרות זאת בדרך כלל לא מציינים את הקבוצה שאודותיה מדובר משום שברור שהכוונה היא לקבוצה שהוגדרה בתור הטווח. אם \(B=\MKim f\).
\(\clubsuit\)
ניתן "לסדר" שכל פונקציה נתונה תהיה על: נצמצם את הטווח שלה לתמונתה ומהגדרת שוויון בין פונקציות לא שינינו את זהות הפונקציה.
\(\clubsuit\)
המסקנה הזו היא הבסיס הרעיוני של המושג העוצמה עבור קבוצות אינסופיות.
\(\clubsuit\)
נשים לב לסימן "\(\mapsto\)" (מסמל את "שליחת" \(x\) ל-\(g\left(f\left(x\right)\right)\) לכל \(x\in A\)) השונה מחברו "\(\rightarrow\)".
\(\clubsuit\)
למעשה, הדרישה היחידה כדי שפונקציה תהיה הפיכה היא היותה חח"ע משום שכפי שראינו לעיל שינוי הטווח של פונקציה אינו משנה את זהותה כל עוד הטווח החדש מכיל את התמונה, ולכן תמיד אפשר להגדיר את הטווח להיות התמונה של הפונקציה ואז היא תהיה על.
הגדרה 8.11. \(f\) תקרא חד-חד-ערכית (להלן גם: חח"ע) אם לכל \(y\in\MKim f\) קיים \(x\in A\)יחיד כך ש-\(f\left(x\right)=y\), במילים אחרות: אם \(x_{1},x_{2}\in A\) מקיימים ש-\(f\left(x_{1}\right)=f\left(x_{2}\right)\) אז \(x_{1}=x_{2}\) או בניסוח שקול לכל \(x_{1},x_{2}\in A\) המקיימים \(x_{1}\neq x_{2}\) מתקיים \(f\left(x_{1}\right)\neq f\left(x_{2}\right)\).
טענה 8.12. תהיינה \(A\) ו-\(B\) שתי קבוצות סופיות ותהא \(f:A\rightarrow B\) פונקציה, אם \(f\) חח"ע אז \(\left|A\right|\leq\left|B\right|\) ואם \(f\) על אז \(\left|B\right|\leq\left|A\right|\).
מסקנה 8.13. בסימוני הטענה הקודמת: אם \(f\) חח"ע ועל אז \(\left|A\right|=\left|B\right|\).
טענה 8.14. תהיינה \(A\) ו-\(B\) שתי קבוצות סופיות שוות גודל (\(\left|A\right|=\left|B\right|\)) ותהא \(f:A\rightarrow B\) פונקציה, \(f\) חח"ע אם"ם \(f\) על.
טענה 8.15. תהיינה \(A\) ו-\(B\) שתי קבוצות, תהא \(f:A\rightarrow B\) פונקציה ותהיינה \(C_{1},C_{2}\subseteq A\) ו-\(D_{1},D_{2}\subseteq B\) תתי-קבוצות; מתקיימים שני הפסוקים הבאים:
אם \(f\) חח"ע אז \(f\left(C_{1}\right)\setminus f\left(C_{2}\right)=f\left(C_{1}\setminus C_{2}\right)\).
הגדרה 8.16. תהא \(g:B\rightarrow C\) נגדיר את ההרכבה של \(g\) על \(f\) כך:\[\begin{align*}
& g\circ f:A\rightarrow C,\\
& g\circ f:x\mapsto g\left(f\left(x\right)\right)
\end{align*}\]
טענה 8.17. תהיינה \(A\), \(B\) ו-\(C\) קבוצות ותהיינה \(f:A\rightarrow B\) ו-\(g:B\rightarrow C\) פונקציות, מתקיימים כל הפסוקים הבאים:
אם \(f\) ו-\(g\) חח"ע אז \(g\circ f\) חח"ע.
אם \(f\) ו-\(g\) על אז \(g\circ f\) על.
אם \(g\circ f\) חח"ע אז \(f\) חח"ע.
אם \(g\circ f\) חח"ע ו-\(f\) על אז \(g\) חח"ע.
אם \(g\circ f\) על אז \(g\) על.
אם \(g\circ f\) על ו-\(g\) חח"ע אז \(f\) על.
טענה 8.18. תהיינה \(A\), \(B\) ו-\(C\) קבוצות ותהיינה \(f:A\rightarrow B\), \(g:A\rightarrow B\) ו-\(h:B\rightarrow C\) פונקציות, אם \(h\) חח"ע ו-\(h\circ g=h\circ f\) אז \(f=g\).
טענה 8.19. תהיינה \(A\), \(B\) ו-\(C\) קבוצות ותהיינה \(f:A\rightarrow B\), \(g:B\rightarrow C\) ו-\(h:B\rightarrow C\) פונקציות, אם \(f\) על ו-\(h\circ f=g\circ f\) אז \(g=h\).
טענה 8.20. הרכבה היא פעולה אסוציאטיבית, כלומר לכל שלוש פונקציות \(f,g,h\) כך ש-\(g\circ f\) ו-\(h\circ g\) מוגדרות היטב מתקיים \(h\circ\left(g\circ f\right)=\left(h\circ g\right)\circ f\).
הגדרה 8.22. נאמר ש-\(f\) היא פונקציה הפיכה אם קיימת \(g:B\rightarrow A\) כך ש-\(f\circ g=\MKid_{B}\) ו-\(g\circ f=\MKid_{A}\).
טענה 8.23. פונקציה היא פונקציה הפיכה אם"ם היא חח"ע ועל.
הגדרה 8.24. אם \(A=B\) ו-\(f\) הפיכה אז נאמר ש-\(f\) היא תמורה על \(A\).
טענה 8.25. אם \(f\) הפיכה אז קיימת \(g:B\rightarrow A\) יחידה כך ש-\(f\circ g=\MKid_{B}\) ו-\(g\circ f=\MKid_{A}\).
הגדרה 8.26. אם \(f\) הפיכה אז נסמן את אותה \(g\) יחידה (במונחי הטענה הקודמת) ב-\(f^{-1}\) ונקרא לה הפונקציה ההופכית של \(f\).
8.3 פונקציות מיוחדות
הגדרה 8.27. הדלתא של קרונקר43ערך בוויקיפדיה: לאופולד קרונקר. הדלתא של קורנקר היא יותר סימון מאשר פונקציה44למרות שמבחינה פורמלית הגבול בין סימון לפונקציה די מטושטש (האם "\(\sqrt{}\)" היא פונקציה או שזהו סימון?), הנקודה המשותפת לשניהם היא החד-ערכיות - יש להם רק פירוש אחד (זו הסיבה לכך שהשורש תמיד חיובי ויש להוסיף לפניו "\(\pm\)" אם רוצים להתייחס לשתי האפשרויות., היא מוגדרת ע"י (לכל \(i,j\in\MKnatural\)):\[
\delta_{ij}:=\begin{cases}
1 & i=j\\
0 & i\neq j
\end{cases}
\]
הגדרה 8.28. פונקציה מציינת תהא \(X\) קבוצה המכילה את \(A\), הפונקציה המציינת של \(A\) (ביחס ל-\(X\)) היא הפונקציה \(\chi_{A}:X\rightarrow\left\{ 0,1\right\} \) המוגדרת ע"י (לכל \(x\in X\)):\[
\chi_{A}\left(x\right):=\begin{cases}
1 & x\in A\\
0 & x\notin A
\end{cases}
\]
\(\clubsuit\)
סימון מקובל נוסף לפונקציה המציינת הוא \(\MKindicator_{A}\).
מסקנה 8.29. תהא \(X\) קבוצה המכילה את \(A\) ואת \(B\), מתקיים (לכל \(x\in X\)):
כעת לאחר שהגדרנו פונקציות נוכל לומר בפשטות שפעולה היא סוג של פונקציה45יש כאן עוד במה לעיין מפני שפעולות על קבוצות צריכות לכאורה שהתחום שלהן יהיה קבוצת הזוגות הסדורים שאיבריהם מקבוצת כל הקבוצות, אך זו יוצרת סתירות ולכן אינה קבוצה..
\(\clubsuit\)
באופן כללי אומרים שפעולה מוגדרת על קבוצה אם לכל "קלט" של מספר האיברים הרצוי מהקבוצה תחזיר הפעולה איבר מן הקבוצה.
\(\clubsuit\)
באופן מסורתי פעולות הנקראות "כפל" מסומנות בעיגול ופעולות הנקראות "חיבור" מסומנות בצלב, וכמו כן המסורת היא שאם מתקיים פילוג אז הפעולה הנקראת "כפל" מקיימת אותו ביחס לפעולה הנקראת "חיבור".
\(\clubsuit\)
באופן מסורתי איבר אדיש של פעולה הנקראת "חיבור" נקרא "אפס" ומסומן ב-"\(0\)" ואילו איבר אדיש של פעולה הנקראת "כפל" נקרא "אחד" ומסומן ב-"\(1\)".
\(\clubsuit\)
השם "איבר אדיש" קצת מפריע לי מבחינה לשונית, הרי זה לא האיבר שאדיש לפעולה אלא היא זו שאדישה אליו.
\(\clubsuit\)
באופן מסורתי התואר "הופכי" ניתן ביחס לפעולות הנקראות "כפל" ותואר "נגדי" ניתן ביחס לפעולות הנקראות "חיבור".
הגדרה 8.30. פעולה חד-מקומית (אונארית) פעולה חד-מקומית (אונארית) היא פונקציה מקבוצה \(A\) לקבוצה \(B\), נהוג לסמן את תוצאת הפעולה על איבר \(a\in A\) ב-\(\oslash a\) (כאשר "\(\oslash\)" הוא הסימון של הפעולה שכמובן יכול להיות מוחלף בכל סימון אחר).
הגדרה 8.31. פעולה דו-מקומית (בינארית) פעולה דו-מקומית (בינארית) היא פונקציה מקבוצת זוגות סדורים \(A\times B\) לקבוצה \(C\) (כלומר פונקציה מהצורה \(\oplus:A\times B\rightarrow C\) כאשר \(A,B,C\) הן קבוצות), נהוג לסמן את תוצאת הפעולה על שני איברים \(a\in A\) ו-\(b\in B\) ב-\(a\oplus b\) (כאשר "\(\oplus\)" הוא הסימון של הפעולה שכמובן יכול להיות מוחלף בכל סימון אחר).
הגדרה 8.32. נאמר שפעולה דו-מקומית "\(\oplus\)" מוגדרת על קבוצה \(A\) אם התחום שלה הוא \(A\times A\) ולכל \(a,b\in A\) מתקיים \(a\oplus b\in A\).
נביא כאן שוב את התכונות שראינו לעיל לגבי פעולות על קבוצות.
תהא \(\oplus:A\times A\rightarrow B\) פעולה דו-מקומית.
הגדרה 8.33. חילוף (קומוטטביות) נאמר ש-\(\oplus\) מקיימת את חוק החילוף (קומוטטיבית) אם לכל \(a,b\in A\) מתקיים \(a\oplus b=b\oplus a\).
הגדרה 8.34. קיבוץ (אסוציאטיביות) נאמר ש-\(\oplus\) מקיימת את חוק הקיבוץ (אסוציאטיבית) אם לכל \(a,b,c\in A\) מתקיים \(\left(a\oplus b\right)\oplus c=a\oplus\left(b\oplus c\right)\).
תהא \(\odot:A\times A\rightarrow B\) גם היא פעולה דו-מקומית.
הגדרה 8.35. פילוג (דיסטריבוטיביות) נאמר ש-\(\odot\) היא מקיימת את חוק הפילוג (דיסטריבוטיבית) ביחס לפעולה \(\oplus\) אם לכל \(a,b,c\in A\) מתקיים \(a\odot\left(b\oplus c\right)=\left(a\odot b\right)\oplus\left(a\odot c\right)\).
הגדרה 8.36. איבר אדיש (ניטרלי) איבר \(e\in A\) יקרא אדיש או ניטרלי ביחס ל-\(\odot\) אם לכל \(a\in A\) מתקיים \(a\odot e=a\) וגם \(e\odot a=a\).
טענה 8.37. אם יש ב-\(A\) איבר אדיש ביחס ל-\(\odot\) אז הוא יחיד.
הגדרה 8.38. איבר הפיך נניח שיש ב-\(A\) איבר אדיש ביחס ל-\(\odot\) ויהי \(e\in A\) איבר אדיש, איבר \(a\in A\) יקרא הפיך אם קיים \(b\in A\) כך ש-\(b\odot a=e=a\odot b\) ו-\(b\) כזה יקרא הופכי או נגדי של \(a\) ביחס ל-\(\odot\).
טענה 8.39. אם הפעולה \(\odot\) מקיימת את חוק הקיבוץ אז לכל איבר הפיך יש הופכי יחיד.
הגדרה 8.40. \(\:\)
תהיינה \(A_{1},A_{2}\subseteq A\), הקבוצה \(A_{1}\oplus A_{2}\) תוגדר ע"י \(A_{1}\oplus A_{2}:=\left\{ a_{1}\oplus a_{2}\mid a_{1}\in A_{1},\ a_{2}\in A_{2}\right\} \)46שימו לב לכך ש-\(A_{1}\oplus A_{2}\subseteq B\)..
תהיינה \(A_{0}\subseteq A\) ו-\(C\) קבוצות, תהא \(\otimes:C\times A\rightarrow B\) פעולה ויהי \(c\in C\); הקבוצה \(c\otimes A_{0}\) תוגדר ע"י \(c\otimes A_{0}:=\left\{ c\otimes a_{0}\mid a_{0}\in A_{0}\right\} \)47גם כאן \(c\otimes A_{0}\subseteq B\)..
הגדרה 8.41. סדרה סופית סדרה סופית של איברים ב-\(B\) היא פונקציה מהצורה \(f:\left\{ n\in\MKnatural\mid n\leq N\right\} \rightarrow B\) עבור \(N\in\MKnatural\) כלשהו; בד"כ מייצגים סדרה כזו באופן מפורש ע"י כתיבת האיברים לפי הסדר בתוך סוגריים מעוגלים48על מנת שלא להתבלבל עם קבוצות שהסוגריים שלהן מסולסלים., כך:\[
\left(f\left(1\right),f\left(2\right),\ldots,f\left(N\right)\right)
\]
הגדרה 8.42. סדרה אינסופית סדרה אינסופית של איברים ב-\(B\) היא פונקציה מהצורה \(a:\MKnatural\rightarrow B\).
\(\clubsuit\)
כמו כל פונקציה נסמן סדרות אינסופיות ע"י אות, למשל \(a\), ואז \(\left(a_{n}\right)_{n=1}^{\infty}\) יהיה הסימון לסדרה (ניתן לסמן סדרה גם ב-\(\left(a_{n}\right)_{n\in\MKnatural}\) ואם נתעצל גם ב-\(\left(a_{n}\right)\)). האות \(n\) מסמנת משתנה סרק של הסדרה, באותה מידה היה יכול להופיע שם \(k\) (או כל אות ואפילו כל קשקוש עקבי אחר), מתקיים \(\left(a_{n}\right)_{n=1}^{\infty}=\left(a_{k}\right)_{k=1}^{\infty}\). נסמן ב-\(a_{n}\) את הפלט שנותנת הפונקציה עבור \(n\), כלומר כמו שעבור פונקציה \(f\) היינו מסמנים ב-\(f\left(x\right)\) את הערך שמקבלת הפונקציה \(f\) ב-\(x\) כך נסמן ב-\(a_{n}\) את הערך שמקבלת הסדרה (הפונקציה) \(\left(a_{n}\right)_{n=1}^{\infty}\) ב-\(n\), \(n\) יקרא האינדקס של \(a_{n}\).
\(\clubsuit\)
ניתן להגדיר סדרות ע"י:
נתינת נוסחה המגדירה לכל \(n\in\MKnatural\) מהו האיבר ה-\(n\)-י בסדרה.
הגדרה רקורסיבית, מגדירים מספר סופי של איברים בסדרה ועבור שאר האיברים מגדירים כיצד כל אחד מהם תלוי באלו שהוגדרו כבר.
ניסוח מילולי מוגדר היטב.
\(\clubsuit\)
לפעמים נתעסק גם בסדרות אינסופיות מהצורות הבאות:
\(a:\MKinteger\rightarrow B\), ואז \(\left(a_{n}\right)_{n=-\infty}^{\infty}\) יהיה הסימון לסדרה (ניתן לסמן גם ב-\(\left(a_{n}\right)_{n\in\MKinteger}\)).
\(a:\left\{ n\in\MKinteger\mid n\geq N\right\} \rightarrow B\) עבור \(N\in\MKinteger\) כלשהו, ואז \(\left(a_{n}\right)_{n=N}^{\infty}\) יהיה הסימון לסדרה.
\(a:\left\{ n\in\MKinteger\mid n\leq N\right\} \rightarrow B\) עבור \(N\in\MKinteger\) כלשהו, ואז \(\left(a_{n}\right)_{n=-\infty}^{N}\) יהיה הסימון לסדרה.
הגדרה 8.43. תהא \(\left(a_{n}\right)_{n=1}^{\infty}\) סדרה. נאמר שסדרה \(\left(b_{k}\right)_{k=1}^{\infty}\) היא תת-סדרה של \(\left(a_{n}\right)_{n=1}^{\infty}\), אם קיימת סדרה \(\left(n_{k}\right)_{k=1}^{\infty}\) עולה ממש49לכל \(k_{1},k_{2}\in\MKnatural\) כך ש-\(k_{1}<k_{2}\) מתקיים \(n_{k_{1}}<n_{k_{2}}\). שכל איבריה טבעיים (סדרת אינדקסים) כך שלכל \(k\in\MKnatural\) מתקיים \(b_{k}=a_{n_{k}}\).
9 סימונים נפוצים
תהא \(A\) קבוצה ותהיינה "\(+\)" ו-"\(\cdot\)" פעולות המוגדרות עליה, לפעולה "\(+\)" נקרא "חיבור" ולפעולה "\(\cdot\)" נקרא "כפל". נניח שפעולות אלו מקימות את חוק הקיבוץ.
האינדקס \(i\) הוא משתנה סרק, באותה מידה היה יכול להופיע שם \(k\) (או כל אות ואפילו כל קשקוש עקבי אחר).
סימון:
נניח שיש ב-\(A\) איברים אדישים ל-\(+\) ול-\(\cdot\), לעיל סימנו סכום ומכפלה סופיים, כעת נרצה להגדיר סכום ומכפלה ריקים - כלומר כאלה שסוכמים/כופלים \(0\) איברים; האיבר האדיש לחיבור יהיה ערכו של סכום ריק ואילו האיבר האדיש לכפל יהיה ערכה של מכפלה ריקה.
\(\clubsuit\)
סכום ומכפלה ריקים נוצרים כאשר אין ל-\(a_{i}\) פירוש לכל \(n\geq i\in\MKnatural\) (נלך ע"פ הסימון שלעיל הסוכם/כופל את \(a_{1},a_{2},\ldots,a_{n}\)), הסיבות השכיחות לכך הן ש-\(A=\emptyset\) או ש-\(n<1\).
סימון:
ולכל \(n\in\MKnatural_{0}\) ולכל \(a\in A\) נסמן\[
a^{n}:=\prod_{i=1}^{n}a
\]סימון זה נקרא חזקה.
\(\clubsuit\)
בפרט \(a^{1}=a\) ו-\(a^{0}=1\).
סימון:
נניח ש-\(a\in A\) איבר הפיך, מכיוון שיש ל-\(a\) הופכי יחיד ניתן לקרוא לו ההופכי של \(a\) ולסמן אותו ב-\(a^{-1}\). לכל \(n\in\MKnatural\) נסמן \(a^{-n}:=\left(a^{-1}\right)^{n}\).
סימון:
נניח שהכפל והחיבור מקיימים את חוקי הקיבוץ והחילוף וש-\(A\) היא קבוצה סופית, יהיו \(a_{1},a_{2},\ldots,a_{n}\) כל האיברים השונים ב-\(A\) ונסמן:\[\begin{align*}
\sum_{a\in A}a & :=a_{1}+a_{2}+\ldots+a_{n}\\
\prod_{a\in A}a & :=a_{1}\cdot a_{2}\cdot\ldots\cdot a_{n}
\end{align*}\]
\(\clubsuit\)
\(a\) הוא משתנה סרק, באותה מידה היה יכול להופיע שם \(b\) (או כל אות ואפילו כל קשקוש עקבי אחר).
\(\clubsuit\)
באופן כללי מקובל לקצר כתיבה של הפעלת פעולה כמה פעמים ע"י כתיבת הסימן של הפעולה בגופן גדול יותר כשמתחתיו נכתב שאנו "מריצים" את הפעולה על פני כל ה-\(x\)-ים שמקיימים תנאי כלשהו (במקרים שלעיל התנאי הוא \(a\in A\)) או שאנו "מריצים" את הפעולה על פני השלמים משלם אחד שמופיע מתחת לסימן הפעולה עד לשלם אחר (כולל) המופיע מעל סימן הפעולה. (במקרים שלעיל "רצנו" מ-\(1\) עד \(n\) אך באותה מידה יכולנו לרוץ מ-\(-3\) עד \(7\)).
\(\clubsuit\)
כלומר קבוצה \(X\) היא בת-מנייה אם"ם קיימת סדרה המכילה את כל איברי \(X\) ללא חזרות.
סימון:
תהא \(X\) קבוצה שכל איבריה הם קבוצות, נסמן:\[\begin{align*}
\bigcup_{x\in X}x & :=\left\{ \begin{array}{c|c}
y & \exists x\in X:y\in x\end{array}\right\} \\
\bigcap_{x\in X}x & :=\left\{ \begin{array}{c|c}
y & \forall x\in X:y\in x\end{array}\right\}
\end{align*}\]אם \(X=\left\{ x_{1},x_{2},\ldots,x_{n}\right\} \) (כלומר \(X\) סופית) מקובלים גם הסימונים:\[\begin{align*}
\bigcup_{i=1}^{n}x_{i} & :=\bigcup_{x\in X}x\\
\bigcap_{i=1}^{n}x_{i} & :=\bigcap_{x\in X}x
\end{align*}\]ואם \(X\) אין-סופית אך בת-מנייה (כלומר ניתן לסדר את איבריה בסדרה) ו-\(\left(x_{i}\right)_{i=1}^{\infty}\) היא סדרת כל האיברים של \(X\)50אין צורך בכך שלא תהיינה בסדרה חזרות על אותו איבר פעמיים, זה לא משנה לחיתוך ולאיחוד של קבוצות. מקובלים גם הסימונים:\[\begin{align*}
\bigcup_{i=1}^{\infty}x_{i} & :=\bigcup_{x\in X}x\\
\bigcap_{i=1}^{\infty}x_{i} & :=\bigcap_{x\in X}x
\end{align*}\]
הגדרה 9.1. תהא \(X\) קבוצה, נאמר ש-\(X\)בת-מנייה אם קיימת פונקציה חח"ע ועל מ-\(\MKnatural\) ל-\(X\), אחרת נאמר ש-\(X\)אינה בת-מנייה.
רוצים לפרגן לי על בניית האתר וכתיבת הסיכומים? אתם מוזמנים לתת טיפ.פורמטים נוספים:
#scrollButton {
position: fixed; /* Keeps the button in a fixed position */
bottom: 0.7em; /* Distance from the bottom */
right: 0.7em; /* Distance from the right */
height: 3.5em;
width: 3.5em;
cursor: pointer;
background-color: #084149;
opacity: 80%;
}
#scrollImage {
position: fixed; /* Keeps the button in a fixed position */
bottom: 0.7em; /* Distance from the bottom */
right: 0.7em; /* Distance from the right */
height: 3.5em;
width: 3.5em;
opacity: 80%;
}
function scrollToTop() {
window.scrollTo({ top: 0, behavior: 'smooth' });
}
דפי האתרדף הביתאודותצור קשרמפת אתרענפים מתמטייםהתחלהאנליזהאלגברהענפים נוספיםאקסיומת השלמותסיכומי הרצאות במתמטיקהדף הביתתרומהאודותהקדשהמפת אתרהתחלהאנליזהאלגברהענפים נוספיםצור קשרעודלאתר הקודםsrayaa.comעִבְלִיקְסתנ"ך ברויאר מוקלט
( function() {
var skipLinkTarget = document.querySelector( 'main' ),
sibling,
skipLinkTargetID,
skipLink;
// Early exit if a skip-link target can't be located.
if ( ! skipLinkTarget ) {
return;
}
/*
* Get the site wrapper.
* The skip-link will be injected in the beginning of it.
*/
sibling = document.querySelector( '.wp-site-blocks' );
// Early exit if the root element was not found.
if ( ! sibling ) {
return;
}
// Get the skip-link target's ID, and generate one if it doesn't exist.
skipLinkTargetID = skipLinkTarget.id;
if ( ! skipLinkTargetID ) {
skipLinkTargetID = 'wp--skip-link--target';
skipLinkTarget.id = skipLinkTargetID;
}
// Create the skip link.
skipLink = document.createElement( 'a' );
skipLink.classList.add( 'skip-link', 'screen-reader-text' );
skipLink.href = '#' + skipLinkTargetID;
skipLink.innerHTML = 'לדלג לתוכן';
// Inject the skip link.
sibling.parentElement.insertBefore( skipLink, sibling );
}() );